%~ http://en.wikipedia.org/wiki/Bisection_method
%~ http://en.wikipedia.org/wiki/Newton%27s_method
%~ http://en.wikipedia.org/wiki/Secant_method
%~ http://en.wikipedia.org/wiki/Regula_falsi
%~ http://en.wikipedia.org/wiki/Rate_of_convergence

\begin{section}{Mini-resumen para el tercer parcial}

\begin{subsection}{Propiedades (Te\'orica)}
\begin{enumerate}
	\item Sean $w(x), p(x): [a, b] \mapsto [a, b]$, $w \in C[a, b], \displaystyle \int_{a}^{b} p(x) \: dx$ existe, $p(x)$ no cambia de signo en $(a, b)$ 
	$\rightarrow$ $\exists \; c \in [a, b]$ tal que $\displaystyle \int_{a}^{b} w(x) p(x) \: dx = w(c) \int_{a}^{b} p(x) \: dx $
	
	\item Sea $g(x): [a, b] \mapsto [a, b]$, $g \in C[a, b]$ $\rightarrow$ $g$ tiene punto fijo en $[a, b]$.\\
	Si adem\'as $|g'(x)| \leq k < 1 \forall x \in [a, b]$ $\rightarrow$ el punto fijo es \'unico en $[a, b]$.
	
	\item Sea $g(x): [a, b] \mapsto [a, b]$, $g \in C[a, b]$ $|g'(x)| \leq k < 1 \forall x \in [a, b]$ 
	$\rightarrow$ $\forall \; p_0 \in [a, b]$ la sucesi\'on $\{p_n\}$ definida como $p_{n+1} = g(p_n)$ converge al \'unico punto fijo de $g$ en $[a,b]$.
	
	\item Sean $g(x): R \mapsto R$, $g(x) \in C^n$ y $p \in R$ con $g'(p) = g''(p) = \dots = g^{r-1}(p) = 0$ y $g^{r}(p) \neq 0$. \\
	Si la sucesi\'on de punto fijo de $g$ converge a $p$ $\rightarrow$ tiene orden de convergencia $r$.
	
	%~ Sean $A \in R^{nxm}$ y $b \in R^n$. 
	\item Sea $A \in R^{nxm}$, entonces $Im(A) \oplus Nu(A^t) = R^n.$
	
	\item La soluci\'on de cuadrados m\'inimos siempre existe.
	
	\item La soluci\'on de cuadrados m\'inimos para el sistema $Ax = b$ es \'unica $\leftrightarrow$ $Nu(a) = {0}$.
	
	\item Sea $A \in R^{nxm}$, entonces $A^tA$ es sim\'etrica, semi-definida positiva.
	
	\item Sea $x \in R^m$ una soluc\'ion de cuadrados m\'inimos para el sistema $Ax = b$, entonces vale que:
		\begin{enumerate}
			\item $A^t r = 0$ donde $r$ es el residuo, definido como $r = Ax - b$.
			\item $A^t A x = A^t b$ (Ecuaciones Normales).
		\end{enumerate}	
	
	
	
	%~ \item 
\end{enumerate}
\end{subsection}

\begin{subsection}{Propiedades (Pr\'acticas)}
\begin{enumerate}
	%~ \item Sea $A \in R^{nxm}$, entonces $<fila_1, \dots, fila_n> \oplus \; Nu(A) = R^m$, y $Im(A) \oplus Nu(A^t) = R^n.$
	\item Sean $u, v \in R^n$, entonces $ \displaystyle {\parallel \negthinspace u + v \negthinspace \parallel}^2_2 = 
	{\parallel \negthinspace u \negthinspace \parallel}^2_2 + {\parallel \negthinspace v \negthinspace \parallel}^2_2 + 
	2< \negthinspace u,v \negthinspace >$ (donde $<\bullet>$ representa el producto interno entre vectores.)
	\item Sean $S \subseteq R^n$, $b \in R$ e $y$ la proyecci\'on ortogonal de $b$ sobre $S$, entonces 
	$\displaystyle \min_{s \in S}{\parallel \negthinspace b - s \negthinspace \parallel}_2 = {\parallel \negthinspace b - y \negthinspace \parallel}_2.$ \\
	Corolario: Dado el sistema $Ax = b$ con $A \in R^{nxm}$ y $b \in R^n$, $x \in R$ es soluci\'on de cuadrados m\'inimos para el sistema  
	$\leftrightarrow$ $x$ es la proyecci\'on ortogonal de $b$ sobre el subespacio $Im(a)$.
	%~ \item 
\end{enumerate}
\end{subsection}

\begin{subsection}{Definiciones}
\begin{enumerate}
	\item Sean $\{\beta_n\}$ y $\{\alpha_n\}$ sucesiones tales que $\displaystyle \lim_{n \rightarrow \infty}{\beta_n \rightarrow 0}$, $\displaystyle \lim_{n \rightarrow \infty}{\alpha_n \rightarrow \alpha}$, si $\displaystyle \exists \; k \in R, \: k > 0$ tal que \\
	$\displaystyle |\alpha_n - \alpha| \leq k \: |\beta_n|$ $\rightarrow$ se dice que la sucesi\'on $\{\alpha_n\}$ tiene orden de convergencia $O(\beta_n).$
	\item Sea $\{x_n\}$ una sucesi\'on tal que $\displaystyle \lim_{n \rightarrow \infty}{x_n \rightarrow x^{*}}$, si vale que 
		\begin{itemize}
			\item $\displaystyle |x_{n+1} - x^{*}| \leq k \: {|x_n - x^{*}|}^{p}$ $\rightarrow$ la convergencia es de orden $p$, $p \geq 1$.
			\item $\displaystyle \lim_{n \rightarrow \infty} \frac{|x_{n+1} - x^{*}|}{{|x_n - x^{*}|}^{p}} = c$ donde $c$ es una constante no nula $\rightarrow$ la convergencia es de orden $p$.
		\end{itemize}	
		\textbf{Casos Particulares de Convergencia} $p = 1$ Lineal, $1 < p < 2$ Superlineal, $p = 2$ Cuadr\'atica.\\
	\item Sea $f: R \mapsto R$, $p \in R$ es punto fijo de $f$ si $f(p) = p.$
	\item Sean $f: R \mapsto R$ y $p_o \in R$, se define la sucesi\'on de punto fijo $\{p_n\}$ como $p_{n+1} = g(p_n)$.
	%~ \item
\end{enumerate}\end{subsection}

\newpage
\begin{subsection}{Integraci\'on Num\'erica}
\par \noindent
Sea la función $f(x)$, $f: R \mapsto R$. Se desea integrar $f$ en el intervalo $[a, b]$. \\
%~ El valor de la integral puede obtenerse de forma no exacta mediante metodos que aproximan $f$ (generalmente usando un polinomio) y luego realizan la integral de la aproximaci\'on (la ventaja es que los polinomios son f\'aciles de integrar). 
$\displaystyle f(x) = P(x) + E(x) \rightarrow $
$\displaystyle \int_{a}^{b} f(x) \: dx = \int_{a}^{b} P(x) \: dx + \int_{a}^{b} E(x) \: dx$

\begin{subsubsection}{F\'ormula de Newton-Cotes}
\begin{enumerate}
	\item Dividir el intervalo $[a, b]$ en $n$ subintervalos iguales de tamaño $h$. \\ Se obtienen $n$ valores de $x_i$, donde $x_i = a + h*i$. 
	\item Aproximar $f$ en cada intervalo usando el polinomio interpolador de Lagrange de grado $k$.
	\item Integrar el polinomio resultante.
\end{enumerate}
\textbf{Casos particulares} $k = 1$ Trapecios, $k = 2$ Simpson.\\

\begin{algorithm}[H]
\caption{Regla Compuesta de Trapecios}
\BlankLine
$\displaystyle \int_{a}^{b} f(x) \: dx = \frac{h}{2} \biggl(f(x_0) + 2 \sum_{j=1}^{n-1} f(x_j) + f(x_n)\biggr) - \frac{h^2}{12} (b-a) f^{(2)}(\mu)$
%~ $\displaystyle \int_{a}^{b} f(x) \: dx = \frac{h}{2} \Bigl(f(x_0) + 2 \sum_{j=1}^{n-1} f(x_j) + f(x_n)\Bigr) - \frac{h^2}{12} (b-a) f^{(4)}(\mu)$
\end{algorithm}

\begin{algorithm}[H]
\caption{Regla Compuesta de Simpson}
\BlankLine
$\displaystyle \int_{a}^{b} f(x) \: dx = \sum_{j=1}^{n/2} \frac{h}{3} \biggl(f(x_{2j-2}) + 4 f(x_{2j-1}) + f(x_{2j})\biggr) - 
\frac{h^5}{90} \frac{n}{2} f^{(4)}(\mu)$
\end{algorithm}

\end{subsubsection}
\end{subsection}

%~ \newpage
\begin{subsection}{M\'etodos Para Aproximar Ceros de Funciones}
\par \noindent
Sea la función $f(x)$, $f: R \mapsto R$, continua.

\begin{subsubsection}{Criterios de Parada}
Para los m\'etodos que aproximan ceros de funciones, es necesario contar con alg\'un criterio de parada, para que el m\'etodo termine de iterar.
\begin{enumerate}
	\item cant\_iteraciones $\leq MAX$
	\item $\displaystyle |x_{n} - x_{n-1}| \leq \varepsilon$
	\item $\displaystyle \frac{|x_{n} - x_{n-1}|}{|x_{n}|} \leq \varepsilon$	
	\item $\displaystyle |f(x_n)| \leq \varepsilon$	
	\item $\displaystyle |f(x_{n}) - f(x_{n-1})| \leq \varepsilon$
	\item $\displaystyle \frac{|f(x_{n}) - f(x_{n-1})|}{|f(x_{n})|} \leq \varepsilon$	
\end{enumerate}
\end{subsubsection}

\begin{subsubsection}{Algoritmos}
\begin{algorithm}[H]
\caption{Bisecci\'on($(a, b)$ intervalo, $x^{(0)} \in R$ punto inicial.)}
\textsl{Requiere} $f(a) . f(b) < 0$
\BlankLine
\While{not criterio\_de\_parada}
{
	$c = \displaystyle \frac{a+b}{2}$
	\BlankLine
	\If{$f(c) == 0$}
	{
		\BlankLine
		return $c$
		\BlankLine
	}
	\Else
	{
		\textsl{Me fijo en cu\'al de los dos subintervalos est\'a el cero}
		\BlankLine
		\If{$f(a).f(c) < 0$}
		{
			\BlankLine
			$b$ = $c$
			\BlankLine
		}
		\Else
		{
			\BlankLine
			$a$ = $c$
			\BlankLine
		}
	}
}
\BlankLine
Tiene convergencia de orden lineal\\
Sea $c_i$ el punto intermedio $c$ obtenido en el paso $i$ de la iteración y sea $r$ la ra\'iz buscada, entonces\\
$\displaystyle |c_i - r| \leq \frac{|a - b|}{2^i}$
\end{algorithm}

\begin{algorithm}[H]
\caption{Newton($x^{(0)} \in R$ punto inicial.)}
\textsl{Requiere} ${x}^{(0)}$ suficientemente 'cerca' de la ra\'iz buscada\\
\textsl{Requiere} $f$ con derivada cont\'inua\\
\textsl{Puede que no converja en muchos casos}
\BlankLine
\While{not criterio\_de\_parada}
{
	${x}^{(n+1)} = {x}^{(n)} - \displaystyle \frac{f({x}^{(n)})}{f'({x}^{(n)})}$
}
\BlankLine
Tiene convergencia de orden cuadr\'atico.\\
\end{algorithm}

\begin{algorithm}[H]
\caption{Secante($x^{(0)}, x^{(1)} \in R$ puntos iniciales.)}
\textsl{Requiere} ${x}^{(0)}, {x}^{(1)}$ suficientemente 'cerca' de la ra\'iz buscada\\
\BlankLine
\While{not criterio\_de\_parada}
{
	${x}^{(n+2)} = {x}^{(n+1)} - \displaystyle f({x}^{(n+1)}) \frac{{x}^{(n+1)} -{x}^{(n)}}{f({x}^{(n+1)}) - f({x}^{(n)})}$
}
\BlankLine
Tiene convergencia de orden superlineal.\\
\end{algorithm}

\newpage
\begin{algorithm}[H]
\caption{Regula Falsi($(a, b)$ intervalo, $x^{(0)} \in R$ punto inicial.)}
\textsl{Requiere} $f(a) . f(b) < 0$
\BlankLine
\While{not criterio\_de\_parada}
{
	$c = \displaystyle \frac{f(b)}{f(b) - f(a)} (b-a)$
	\BlankLine
	\If{$f(c) == 0$}
	{
		\BlankLine
		return $c$
		\BlankLine
	}
	\Else
	{
		\textsl{Me fijo en cu\'al de los dos subintervalos est\'a el cero}
		\BlankLine
		\If{$f(a).f(c) < 0$}
		{
			\BlankLine
			$b$ = $c$
			\BlankLine
		}
		\Else
		{
			\BlankLine
			$a$ = $c$
			\BlankLine
		}
	}
}
\end{algorithm}

\end{subsubsection}
\end{subsection}

%~ \newpage
\begin{subsection}{Cuadrados M\'inimos}
\par \noindent
Se tienen $n$ puntos de la forma $\{x_i, y_i\}$ y $F$ una familia de funciones. \\
%~ tal que aproxime de la mejor manera posible los puntos
Se busca $f' \in F$ tal que $\displaystyle \min_{f \in F}{\sum_{i = 1}^n {|f(x_i) - y_i|}^2_2} = 
\sum_{i = 1}^n {| \negthinspace f'(x_i) - y_i \negthinspace |}^2_2$. \\
En general la funci\'on $f$ tendr\'a $m$ par\'ametros lineales a determinar $(m < n)$ y ser\'a de la forma \\
$\displaystyle f(x) = a_1 \Phi_1(x) + \dots + a_m \Phi_m(x)$ donde $\Phi_1, \dots, \Phi_m$ son funciones conocidas.

\begin{subsubsection}{Forma Matricial}
$\displaystyle A = \begin{pmatrix} 
\Phi_1(x_1) & \ldots & \Phi_m(x_1) \\  
\vdots & \ddots & \vdots \\  
\Phi_1(x_n) & \ldots & \Phi_m(x_n) \\  
\end{pmatrix} \in R^{nxm} 
\qquad
x = \begin{pmatrix} a_1 \\ \vdots \\ a_m \end{pmatrix} \in R^{m}
\qquad
b = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix} \in R^{n}$ 
\paragraph{}
Se busca $x \in R^m$ tal que $\displaystyle {\parallel \negthinspace Ax - b \negthinspace \parallel}^2_2$ es m\'inima.
\end{subsubsection}

%~ \begin{algorithm}[H]
%~ \caption{}
%~ \textsl{Requiere}
%~ \BlankLine
%~ \end{algorithm}


\end{subsection}

\end{section}
